package leetcode;

/**
 * @author caifangyi
 * @date 2022/7/22
 */

import java.util.Arrays;
import java.util.stream.Collectors;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * 
 * 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
 *
 * 如果数组中不存在目标值 target，返回[-1, -1]。
 *
 * 你必须设计并实现时间复杂度为O(log n)的算法解决此问题。
 *
 * 
 *
 * 示例 1：
 *
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 * 示例2：
 *
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 * 示例 3：
 *
 * 输入：nums = [], target = 0
 * 输出：[-1,-1]
 * 
 *
 * 提示：
 *
 * 0 <= nums.length <= 105
 * -109<= nums[i]<= 109
 * nums是一个非递减数组
 * -109<= target<= 109
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

class Day0034 {

    public static void main(String[] args) {
        int nums[] = {5,7,7,8,8,10};
        Solution solution = new Solution();
        int[] ints = solution.searchRange(nums, 7);
        String collect = Arrays.stream(ints).mapToObj(value -> String.valueOf(value)).collect(Collectors.joining(","));
        System.out.println(collect);
    }

    static class Solution {
        public int[] searchRange(int[] nums, int target) {
            int l = binarySearch(nums, target);
            int r = binarySearch(nums, target + 1);
            if(l==nums.length||nums[l]!=target){
                return new int[]{-1, -1};
            }
            return new int[]{l, r-1};
        }

        private int binarySearch(int[] nums, int target) {
            int l = 0, r = nums.length;
            while (l<r){
                int mid = l + (r - l)/2;
                if(nums[mid] >= target){
                    r = mid;
                }else if(nums[mid] < target){
                    l = mid + 1;
                }
            }
            return l;
        }
    }
}
